package com.ycsyxt.guide;

import java.util.Arrays;

/**
 * 归并排序
 *
 * @author ycs(15241496739 @ 163.com)
 * @date 2022/6/5
 **/
public class Class6 {
    public static int[] merge_sort(int[] to_sort) {
        if (to_sort.length == 1) {
            return to_sort;
        }
        int mid = to_sort.length / 2;
        int[] left = Arrays.copyOfRange(to_sort, 0, mid);
        int[] right = Arrays.copyOfRange(to_sort, mid, to_sort.length);
        left = merge_sort(left);
        right = merge_sort(right);

        return merge(left, right);
    }

    public static int[] merge(int[] left, int[] right) {
        int[] merged = new int[left.length + right.length];
        int mi = 0, ai = 0, bi = 0;
        while (ai < left.length && bi < right.length) {
            if (left[ai] <= right[bi]) {
                merged[mi] = left[ai];
                ai++;
            } else {
                merged[mi] = right[bi];
                bi++;
            }
            mi++;
        }
        for (int i = ai; i < left.length; i++) {
            merged[mi] = left[i];
            mi++;
        }
        for (int i = bi; i < right.length; i++) {
            merged[mi] = right[i];
            mi++;
        }
        return merged;
    }
    public static void main(String[] args) {
        int[] sort = new int[] {1,2,5,8,3,4,6};
        sort = merge_sort(sort);
        System.out.println(Arrays.toString(sort));
    }
}
